Integrating expert systems and mathematical programming: An example in infrastructure management

This report describes the integration of an integer programming model and an expert system. The application involves selecting bridges for repair/maintenance with the State of New Jersey. The integrated system has been designed for a PC environment using the GAMS/ZOOM optimization package in conjunction with the RuleMaster expert system in a loosely coupled fashion. The advantages of this approach are discussed. Testing has been carried out with data generated from a portion of New Jersey's highway system.Statistics and Operations Research Series Report SOR-88-10, April 1989)     

An upper bound for the Folkman number F(3, 3; 5)

Let F(p, q; r) denote the minimum number of vertices in a graph G that has the properties (1) G contains no complete subgraph on r vertices, and (2) any green-red coloring of the edges of G yields a green complete subgraph on p vertices or a red complete subgraph on q vertices. Folkman proved the existence of F(p, q; r) whenever r > max {p, q}. We show F(3, 3; 5) ≤ 17, improving a bound due to Irving and an earlier bound due to Graham and Spencer. © 1993 John Wiley & Sons, Inc.     

Better lower bounds on detecting affine and spherical degeneracies

We show that in the worst case, Ω(n ^d ) sidedness queries are required to determine whether a set ofn points in ℝ ^d is affinely degenerate, i.e., whether it containsd+1 points on a common hyperplane. This matches known upper bounds. We give a straightforward adversary argument, based on the explicit construction of a point set containing Ω(n ^d ) “collapsible” simplices, any one of which can be made degenerate without changing the orientation of any other simplex. As an immediate corollary, we have an Ω(n ^d ) lower bound on the number of sidedness queries required to determine the order type of a set ofn points in ℝ ^d . Using similar techniques, we also show that Ω(n ^d+1) in-sphere queries are required to decide the existence of spherical degeneracies in a set ofn points in ℝ ^d . An earlier version of this paper was presented at the 34th Annual IEEE Symposium on Foundations of Computer Science [8]. This research has been supported by NSF Presidential Young Investigator Grant CCR-9058440.     

A six-dimensional superspace approach to extended superfields

We present an improved formalism for treating six-dimensional superspace and apply it to writing linearized N = 2 Yang-Mills theory and the N = 2 relaxed hypermultiplet in SU(2) covariant forms that are simpler than the known four-dimensional forms.     

Designer gene networks: Towards fundamental cellular control

The engineered control of cellular function through the design of synthetic genetic networks is becoming plausible. Here we show how a naturally occurring network can be used as a parts list for artificial network design, and how model formulation leads to computational and analytical approaches relevant to nonlinear dynamics and statistical physics. We first review the relevant work on synthetic gene networks, highlighting the important experimental findings with regard to genetic switches and oscillators. We then present the derivation of a deterministic model describing the temporal evolution of the concentration of protein in a single-gene network. Bistability in the steady-state protein concentration arises naturally as a consequence of autoregulatory feedback, and we focus on the hysteretic properties of the protein concentration as a function of the degradation rate. We then formulate the effect of an external noise source which interacts with the protein degradation rate. We demonstrate the utility of such a formulation by constructing a protein switch, whereby external noise pulses are used to switch the protein concentration between two values. Following the lead of earlier work, we show how the addition of a second network component can be used to construct a relaxation oscillator, whereby the system is driven around the hysteresis loop. We highlight the frequency dependence on the tunable parameter values, and discuss design plausibility. We emphasize how the model equations can be used to develop design criteria for robust oscillations, and illustrate this point with parameter plots illuminating the oscillatory regions for given parameter values. We then turn to the utilization of an intrinsic cellular process as a means of controlling the oscillations. We consider a network design which exhibits self-sustained oscillations, and discuss the driving of the oscillator in the context of synchronization. Then, as a second design, we consider a synthetic network with parameter values near, but outside, the oscillatory boundary. In this case, we show how resonance can lead to the induction of oscillations and amplification of a cellular signal. Finally, we construct a toggle switch from positive regulatory elements, and compare the switching properties for this network with those of a network constructed using negative regulation. Our results demonstrate the utility of model analysis in the construction of synthetic gene regulatory networks. (c) 2001 American Institute of Physics.     

Selective high-resolution electrodeposition on semiconductor defect patterns

We report a new principle and technique that allows one to electrodeposit material patterns of arbitrary shape down to the submicrometer scale. We demonstrate that an electrochemical metal deposition reaction can be initiated selectively at surface defects created in a p-type Si(100) substrate by Si (++) focused ion beam bombardment. The key principle is that, for cathodic electrochemical polarization of p-type material in the dark, breakdown of the blocking Schottky barrier at the semiconductor/electrolyte interface occurs at significantly lower voltages at implanted locations than for an unimplanted surface. This difference in the threshold voltages is exploited to achieve selective electrochemical deposition.     

Large-scale, density functional theory-based screening of alloys for hydrogen evolution

A general scheme for the screening of heterogeneous catalysts using density functional theory (DFT) calculations is presented, and the scheme is illustrated with a search for catalysts for the hydrogen evolution reaction. Simple techniques to estimate the activity of binary surface and bulk alloys for this reaction are described, and several computational tests for stability in reaction environments are presented. Careful application of these activities and stability criteria to a database of DFT calculations on ∼750 binary transition metal alloys leads to the identification of several surface and bulk alloys that are predicted to perform comparably to platinum, the canonical hydrogen evolution catalyst. This study marks the first use of full DFT calculations for high-throughput screening of transition metal catalysts.     

Lower bounds on Ricci curvature and quantitative behavior of singular sets

Let Y ⁿ denote the Gromov-Hausdorff limit $M^{n}_{i}\stackrel{d_{\mathrm{GH}}}{\longrightarrow} Y^{n}$ of v-noncollapsed Riemannian manifolds with ${\mathrm{Ric}}_{M^{n}_{i}}\geq-(n-1)$ . The singular set $\mathcal {S}\subset Y$ has a stratification $\mathcal {S}^{0}\subset \mathcal {S}^{1}\subset\cdots\subset \mathcal {S}$ , where $y\in \mathcal {S}^{k}$ if no tangent cone at y splits off a factor ? ^k+1 isometrically. Here, we define for all η>0, 0<r≤1, the k-th effective singular stratum $\mathcal {S}^{k}_{\eta,r}$ satisfying $\bigcup_{\eta}\bigcap_{r} \,\mathcal {S}^{k}_{\eta,r}= \mathcal {S}^{k}$ . Sharpening the known Hausdorff dimension bound $\dim\, \mathcal {S}^{k}\leq k$ , we prove that for all y, the volume of the r-tubular neighborhood of $\mathcal {S}^{k}_{\eta,r}$ satisfies ${\mathrm {Vol}}(T_{r}(\mathcal {S}^{k}_{\eta,r})\cap B_{\frac{1}{2}}(y))\leq c(n,{\mathrm {v}},\eta)r^{n-k-\eta}$ . The proof involves a quantitative differentiation argument. This result has applications to Einstein manifolds. Let $\mathcal {B}_{r}$ denote the set of points at which the C ²-harmonic radius is ≤r. If also the $M^{n}_{i}$ are Kähler-Einstein with L ₂ curvature bound, $\| Rm\|_{L_{2}}\leq C$ , then ${\mathrm {Vol}}( \mathcal {B}_{r}\cap B_{\frac{1}{2}}(y))\leq c(n,{\mathrm {v}},C)r^{4}$ for all y. In the Kähler-Einstein case, without assuming any integral curvature bound on the $M^{n}_{i}$ , we obtain a slightly weaker volume bound on $\mathcal {B}_{r}$ which yields an a priori L _p curvature bound for all p<2. The methodology developed in this paper is new and is applicable in many other contexts. These include harmonic maps, minimal hypersurfaces, mean curvature flow and critical sets of solutions to elliptic equations.     

Tracing Compressed Curves in Triangulated Surfaces

A simple path or cycle in a triangulated surface is normal if it intersects any triangle in a finite set of arcs, each crossing from one edge of the triangle to another. A normal curve is a finite set of disjoint normal paths and normal cycles. We describe an algorithm to “trace” a normal curve in $O(\min \{ X, n^2\log X \})$ O ( min { X , n 2 log X } ) time, where $n$ n is the complexity of the surface triangulation and $X$ X is the number of times the curve crosses edges of the triangulation. In particular, our algorithm runs in polynomial time even when the number of crossings is exponential in $n$ n . Our tracing algorithm computes a new cellular decomposition of the surface with complexity $O(n)$ O ( n ) ; the traced curve appears in the 1-skeleton of the new decomposition as a set of simple disjoint paths and cycles. We apply our abstract tracing strategy to two different classes of normal curves: abstract curves represented by normal coordinates, which record the number of intersections with each edge of the surface triangulation, and simple geodesics, represented by a starting point and direction in the local coordinate system of some triangle. Our normal-coordinate algorithms are competitive with and conceptually simpler than earlier algorithms by Schaefer et al. (Proceedings of 8th International Conference Computing and Combinatorics. Lecture Notes in Computer Science, vol. 2387, pp. 370–380. Springer, Berlin 2002; Proceedings of 20th Canadian Conference on Computational Geometry, pp. 111–114, 2008) and by Agol et al. (Trans Am Math Soc 358(9): 3821–3850, 2006).